\chapter{Introduction}
\label{chap:introduction}
%\addcontentsline{toc}{chapter}{Introduction}


\emph{Planning} is the process of constructing \emph{action sequences} that need to be executed in order to reach a selected \emph{goal} from a given \emph{premise}. Software systems, capable of accomplishing this task are called \emph{planners} or \emph{planning systems}. The field of artificial intelligence that works on designing and implementing such tools is called \emph{automated planning}. As Vrakas and Vlahavas~\cite{vrakas2008ai} writes, this well developed area is nearly as old, as informatics itself. Its roots are considered to be in the 1960s, with the \emph{General Problem Solver} program done by Newel, Simon, et al~\cite{newel1956gps}, but there are still yet unexplored areas, and new places of application.\footnote{For a less brief introduction to the principles of planning, read Ghallab, Nau, and Traverso's \emph{Automated Planning: Theory and practise}~\cite{2004automatedPlanning}.}

Planning is an important task in nearly every computer game; however it was never taken as a fundamental concept. The general approach is to create a custom built planner for the specific tasks that occur in the game under development. Such narrow focus is both their strength, and weakness. The small domain implies, they are fast, and in addition, their relatively low complexity makes them easy to write. On the other hand they are hard to extend, and require maintenance. 

Our theory was, that just as with engines, a game programmer does not need a custom tool; that off-the-shelf alternatives are capable of providing comparable results in virtually zero development time. As opposed to their customized counterparts, general purpose tools are inherently slower, but also more flexible, and most importantly, they are written, and maintained by third party professionals.

We decided to write a whole game around the use of planners. We decided to exploit them in two distinct way, namely to generate the game levels, and in the gameplay to act as the decision making tool of the acting agents.

A typical chore when making a game is level design. In modern games it is one of the most time consuming works of the development, however several parts of the process does not require actual creativity, only calculating power. In the developer community there were already some attempts to automate level creation, for example by random generating them (we will return to these projects at section~\ref{sec:relatedWork}, and again in section~\ref{sec:futureWorks}).

We were looking for a way to pass the task of level creation on external planners. While we didn't want to completely replace the human hand, we tried to provide a tool to generate varied player challenges on a single layout provided by the developer.

Another place where planning may come handy is agent control. It is a well studied field with many different approaches, to get a good overview, we recommend~\cite{franklin2001artificialMinds} as a good starting point. In computer games the usual approach is to go with \emph{finite-state machines} or \emph{decision trees}. They are both relatively simple, and straightforward to use. In comparison with planners, their weakness is their rigidity; every possibility must be accounted for by the programmer, while a planning system may create seemingly rational sequences of actions without the developer ever considering them.

We choose the program genre in a way to benefit the most from the problem solving capabilities of our selected tools. Our program is basically a logic game, more precisely an \emph{anticipation game}. In our previous report Rudolf Kadlec summarized it as follows:

\begin{longtable}{|p{0.9\textwidth}}
``Imagine you play a game where the main agent has a mission that he must accomplish. He creates a plan for this mission but due to incomplete knowledge of the environment there will be some pitfalls in his plan. The human player has more complete knowledge of the environment, thus when observing execution of the agent's plan, he can anticipate these pitfalls. Once he identifies a pitfall, he can modify the environment so that the agent has to replan and the new plan avoids this pitfall. The player influences the agent only indirectly through changes of the environment.''\cite{burglarICAPSsubmission}
\end{longtable}

In our implementation the protagonist is a burglar in a foreign building and the pitfalls are represented as the security system. The player slips into the role of a god-like being disabling cameras, locking, or opening doors to avoid the otherwise inevitable capture of the burglar.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Related work}
\label{sec:relatedWork}

To our knowledge so far no game have set planning as its core principle; nevertheless there are plenty of projects, and experiments that from some point of view are similar to ours. They are either trying to make the level designer's work easier or they take planning to the game industry.

\subsection{Random generated levels}

Random generation is a widely used, and explored\footnote{Mostly documented only on developer community sites, like http://roguebasin.roguelikedevelopment.org, (10.03.2012)} concept from the simplest card games to sophisticated \emph{dungeon crawlers}, for example the \emph{Diablo} series\footnote{Home page: http://us.battle.net/d3/en, (10.03.2012)} or \emph{Torchlight 2}\footnote{Home page: http://www.torchlight2game.com, (10.03.2012)}.
In such games the program generates each level of the dungeon by assembling modular ``chunks'' of the game environment. Each part is designed by hand; they can contain scripted events and interactive objects. This approach is intended to create dungeons with always differing, but purposeful design.

Our method differs in the basic principles: while they chain the challenges together into a new world layout, we take the layout as given, and fill it with challenges.

\subsection{Off-line planning}

There are a few projects that explored the off-line use of planners before us, but in a different manner. While we were concentrating on graph problems in our level generator the following papers approached the problem from the perspective of story creation.

Li, and Riedl~\cite{li2010offline} used planning methods to generate backstories for role playing game characters.
Extended work was done on the fields of \emph{interactive storytelling}~\cite{porteous2009controlling,porteous2011visual} by Porteous, Cavazza et al. They concentrate on translating the task of good story composition to good plan creating.
Probably the most similar to our work is the automatic storyboard generation, which produces \emph{Hitman 2}\footnote{No official site found in the time of writing (10.03.2012)}
 missions in a comic strip format by Pizzi, Cavazza, et al~\cite{pizzi2008automatic}. Here the designer uses planning to explore the possible solutions, if he finds some unsatisfactory ones, he changes the initial level setup to fix the problem. 

\subsection{On-line planning}

Just as in development we tried to use off-the-shelf, \emph{PDDL}\cite{edelkamp2003pddl} (Planning Domain Definition Language) compatible planners in our gameplay; we have found no commercial use of such tools. The planning systems preferred by the game industry are \emph{Goal-Oriented Action Planning}~(GOAP) and \emph{Hierarchical task network}~(HTN).

GOAP~\cite{orkin2003applying,orkin2006three} is a simplified \emph{STRIPS}-like~\cite{fikes1971strips} planning architecture specifically designed for real-time control of autonomous characters. Its success illustrates the list of commercial games using this planner\footnote{for more details, see http://web.media.mit.edu/$\sim$jorkin/goap.html (23.11.2011)}. HTN organizes tasks into hierarchical layers; its use in game environments was demonstrated by Hoang, Mu{\~n}oz-Avila, et al~\cite{hoang2005hierarchical, munoz2006coordinating}.

We found very few uses of real STRIPS-like PDDL compatible planners directly in gameplay. The works of Bartheye and Jacopin~\cite{bartheye2009real,bartheye2008connecting} are centered around real time generation of plans in situations where fluent gameplay is essential. In accord with International Planning Competition challenges there have been recently proposed benchmark tasks motivated by needs of First Person Shooter (FPS) games by Vassos and Papakonstantinou~\cite{vassos2011simplefps}. Opposed to the above mentioned works our proposed game genre has a more relaxed pace and true real time planning was not a priority to us. We built our program with logical challenges in mind and gave up some of the premises that current FPS games maintain, like the agent's full knowledge of the level layout.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Overview of the following chapters}

The rest of the thesis continues as follows. In chapter~\ref{chap:gameWorld}: Game world we describe the characters and the environment where our game takes place. The next chapter, titled Gameplay (chapter~\ref{chap:gameplay}) shows the program from the player's perspective. In chapter~\ref{chap:problemDefinition}: Problem definition we detail the formal definition of the program's concept. Chapter~\ref{chap:agentControl}: Agent control describes how we integrated the planners into the gameplay. The following chapter~\ref{chap:creatingGameLevels}: Creating game levels contains our approach towards level design. In chapter~\ref{chap:implementation}: Implementation we briefly describe the third party libraries we used through the development and the basic structure of the program. The used planners and tests we conducted on them can be found in chapter~\ref{chap:planners}: Planners. We finish the thesis with chapters~\ref{chap:playerResponses}: Player responses about users' experience, and chapter~\ref{chap:conclusion}: Conclusion.

